/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Aug 27, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, find the maximum path sum.
 * 
 *              The path may start and end at any node in the tree.
 * 
 *              For example: Given the below binary tree,
 * 
 *                1
 *               / \ 
 *              2   3 
 *              
 *             Return 6.
 */
public class BinaryTreeMaximumPathSum {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	}
	
	// begin
	int max; 
	
	public int maxPathSum(TreeNode root) {
		max = (root == null) ? 0 : root.val;
		findMax(root);
		
		return max;
	}
 
	private int findMax(TreeNode node) {
		if (node == null)
			return 0;
 
		// recursively get sum of left and right path
		int left = Math.max(findMax(node.left), 0);
		int right = Math.max(findMax(node.right), 0);
 
		// update maximum here
		max = Math.max(node.val + left + right, max);
 
		// return sum of largest path of current node
		return node.val + Math.max(left, right);
	}

	@Test
	public void test() {
		TreeNode n1 = new TreeNode(-1);
		TreeNode n2 = new TreeNode(-2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(-1);
		TreeNode n6 = new TreeNode(-1);
		TreeNode n7 = new TreeNode(5);
		
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.right = n6;
		n6.right = n7;
		
		System.out.println(maxPathSum(n1));
	}
}
